1. Field of the Invention
This invention relates generally to error correction techniques, and more particularly to improved methods for correcting errors in data that is read from a physical medium.
2. Description of the Related Art
To maintain an acceptable level of data integrity, many types of error correction codes are commonly used. Generally, data that is stored on a physical media is encoded with data patterns that enable decoding systems to identify and correct errors that may be introduced during a reading, processing or transferring operation. In optical storage media applications, there are many factors that contribute to the introduction of errors. Some factors include media defects (i.e., such as damaged compact disc surfaces), electronic noise, component failures, poor electrical connections, and deterioration due to age. Because errors are so common, there is an ever increasing need for error correction systems that are powerful enough to correct complex error combinations, and fast enough to meet the performance demands of today""s computer systems.
In optical data storage media, error correction techniques and systems are typically performed on a xe2x80x9cper-famexe2x80x9d basis, where each frame has its data arranged in an array format. For ease of discussion, FIG. 1A shows a data frame 100 having a plurality of data bytes 104a and associated check bytes 104b. The data bytes 104a are arranged in Q code words 110a, 110b, and 110c, which are aligned in a vertical dimension along the data frame 100. In a similar manner, P code words 112a and 112b are aligned in a horizontal dimension along the data frame 100. When an error data byte 106 is detected in the data frame 100 after performing an error correction code (ECC) operation, the check bytes 104b will reflect a non-zero syndrome 108, which indicates the presence of an error.
For example, when the error data byte 106 is detected after performing the ECC operation, non-zero syndromes 108 will be detected along both a Q code word 110a and a P code word 112b. In a similar manner, when error data bytes 116a and 116b are detected in the data frame 100 after performing an ECC operation, respective non-zero syndromes 108 will be detected in the check bytes in both the Q code words 110b and 110c, and the P code word 112a. As should be familiar to those skilled in the art of error correction techniques, the above described ECC operations implement well known two-dimensional (i.e., Q and P dimensions) product code to protect the data that is stored on the media. For more information on product code, reference may be made to a book entitled xe2x80x9cError-Correcting Codesxe2x80x9d by W. Wesley Peterson and E. J. Weldon, Jr. (1972), and a book entitled xe2x80x9cPractical Error Correction Design for Engineersxe2x80x9d by Neal Glover and Trent Dudly, p. 271 (1991). These books are herein incorporated by reference in their entirety.
When product code with two check bytes is used, there are four commonly used tools that may be implemented in the correction of detected error data bytes. For example, there is single error correction (SEC) system where the location and pattern are not known, that may be used for the P dimension (i.e., SEC P) and the Q dimension (i.e., SEC Q). There is also what is known as an erasure correction (EC) system where the location is known, but the pattern is not, which is also implemented in the P dimension (i.e., EC P) and in the Q dimension (i.e., EC Q).
In general, one or more of the four error correction systems may be used in correcting errors. However, an error correction system is generally best selected depending on the number of errors that are detected along a particular code word. For example, the single error correction (SEC) system is optimized to correct only one error data byte at a time along a particular code word. This is true because single error correction systems are only required to solve simple syndrome equations.
On the other hand, when there is more than one error data byte along a particular code word, the simple syndrome equations may not work, and in some cases, additional errors may be introduced. To remedy this, erasure correction (EC) systems that implement more complex syndrome equations are used. In EC correction systems, the syndrome equations are solved by plugging in the location (L) values for each of the code words in which the error data bytes are detected. By way of example, in FIG. 1A two error data bytes 116a and 116b lie along the P code word 112a. When the locations L for the Q code words 110b and 110c are plugged into the syndrome equations of FIG. 1B, the error data bytes can be corrected.
Single error correction (SEC) systems are therefore best used in cases where there is only one error data byte along a particular code word, and when there is more than one error data byte along a particular code word, the erasure correction (EC) systems should be used. Unfortunately, conventional correction schemes are not configured to use the best correction system to process each unique error pattern, and therefore, often fail to produce an acceptable level of correction. In fact, most hardware error correction implementations are programmed to correct a given data frame 100 with only one or two error correction systems, without first examining which scheme is best suited for the detected errors. As a result, many correctable errors will necessarily be marked as un-correctable because only a subset of all possible correction systems will be performed.
Although software-only error correction can be used to increase the number of error correction systems used in correcting a given data frame 100, software error correction is very computationally intensive. As a result, software-only error correction has the known detrimental effect of further burdening a computer""s microprocessor. In addition, most optical drive applications will also require an additional microprocessor, microcontroller, or digital signal processor to perform some of the correction operations. Consequently, software-only implementations have been less than adequate for commercial use.
In view of the foregoing, what is needed is an error correction system that is implemented in hardware, yet provides the flexibility of using custom correction systems that are optimally suited to correct the errors detected in a particular data frame.
Broadly speaking, the present invention fills these needs by providing a method and apparatus for performing intelligent error correction. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium. Several inventive embodiments of the present invention are described below.
In one embodiment, a method for error code correction using product code is disclosed. The method includes: (a) reading a data frame and associated check bytes from a media; (b) generating an error correction model for the data frame and associated check bytes, where the error correction model is defined by non-zero syndromes in the check bytes of Q dimension code words and P dimension code words of the data frame; (c) examining the generated error correction model; and (d) correcting the data frame using a combination of error correction systems that are selected based on the examining of the generated error correction model.
In another embodiment, an apparatus for performing error correction using product code stored on a physical medium is disclosed. The apparatus includes an error correction code sequencer, and a memory block that is integrated with the error correction code sequencer. The memory block is configured to store a plurality of combinations of error correction systems. The apparatus further includes a decoder processor that is in communication with the physical medium, and a digital signal processor that is in communication with a programmable memory device. The programmable memory device is configured to select one of the plurality of combinations of error correction systems when the error correction code sequencer examines an error correction model of a data frame that is read from the physical medium.
In yet a further embodiment, a system for error code correction using product code is disclosed. The system includes means for reading a data frame and associated check bytes from a media, and means for generating an error correction model for the data frame and associated check bytes. The error correction model is defined by non-zero syndromes in the check bytes of Q dimension code words and P dimension code words of the data frame. The system further includes means for examining the generated error correction model, and means for correcting the data frame using a combination of error correction systems that are selected based on the examining of the generated error correction model.
In still a further embodiment, a method for encryption protecting data stored on an optical media is disclosed. The data is encrypted with a custom error pattern. The method includes reading the optical media to obtain a special code that contains the custom error pattern. Transferring the special code to a host computer to enable future access to the optical media by the host computer that has the special code. The method further includes error correcting at least one data frame of the optical media using a combination of error correction systems that are predetermined to correct the custom error pattern. Preferably, the error correcting is allowed when the host computer that has the special code makes a request for the at least one data frame of the optical media.
In another embodiment, a system for encryption protecting data that is stored on an optical media is disclosed. The data is first encrypted with a custom error pattern. The system includes means for reading the optical media to obtain a special code that contains the custom error pattern, and means for transferring the special code to a host computer to enable future access to the optical media by the host computer that has the special code. The system further includes means for error correcting at least one data frame of the optical media using a combination of error correction systems that are predetermined to correct the custom error pattern.
Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.